// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-11 19:34
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DynamicPlan;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

@SuppressWarnings("ALL")
public class CountHighestScoreNodeT {

    //使用两个数组保存二叉树的左右节点，索引为父节点
    int[] left, right;
    //最大分数, 注意溢出，这里用 long
    long maxScore;
    //最大分数量
    int cnt;
    //整棵树大小
    int n;

    public int countHighestScoreNodes(int[] parents) {
        n = parents.length;
        left = new int[n];
        right = new int[n];
        //初始化树的表示，-1表示空节点
        Arrays.fill(left, -1);
        Arrays.fill(right, -1);
        //构建树的表示
        for (int i = 1; i < n; i++) {
            //填充左右节点无所谓，这里优先填左节点
            if (left[parents[i]] == -1) {
                left[parents[i]] = i;
            } else {
                right[parents[i]] = i;
            }
        }
        //dfs处理更新相关值
        dfs(0);
        return cnt;
    }

    //返回以此节点为根节点的子树的大小
    private long dfs(int node) {
        if (node == -1) {
            return 0;
        }
        //dfs 获取左右子树大小
        long leftSize = dfs(left[node]), rightSize = dfs(right[node]);
        //计算三个联通块的乘积
        long score = Math.max(leftSize, 1) * Math.max(rightSize, 1) * Math.max(n - leftSize - rightSize - 1, 1);
        if (score == maxScore) {
            cnt++;
        } else if (score > maxScore) {
            maxScore = score;
            cnt = 1;
        }
        return leftSize + rightSize + 1;
    }


    @Test
    public void shout() {
        int[] test = {-1, 2, 0, 2, 0};
        System.out.println(countHighestScoreNodes(test));
    }

}
